package org.example.SolutionNew002;

import java.util.HashMap;
import java.util.Map;

public class LinkedList11 {
    public static void main(String[] args) {
        LinkedList11 obj = new LinkedList11();
        Node head1 = new Node(7);
        head1.next = new Node(13);
        head1.random=null;
        head1.next.random=head1;
        head1.next.next = new Node(11);
        head1.next.next.next = new Node(10);
        head1.next.next.next.random=head1.next.next;
        head1.next.next.next.next = new Node(1);
        head1.next.next.next.next.random=head1;
        head1.next.next.random=head1.next.next.next.next;
        Node res=obj.copyRandomList(head1);
        while(res!=null){
            System.out.println(res.val);
            res=res.next;
        }
    }

    public Node copyRandomList1(Node head) {
        //难点在于如何在链表中来来回回，我想到的是使用一个map来储存
        if (head == null)  return null;
        Node res=new Node(head.val);
        Map<Node,Node> map=new HashMap<>();
        Node h=head;
        map.put(h,res);
        while(h!=null){
            if(h.next!=null){
                if(!map.containsKey(h.next)){
                    map.put(h.next,new Node(h.next.val));
                }
                map.get(h).next=map.get(h.next);
            }else{
                map.get(h).next=null;
            }
            if(h.random!=null){
                if(!map.containsKey(h.random)){
                    map.put(h.random,new Node(h.random.val));
                }
                map.get(h).random=map.get(h.random);
            }else{
                map.get(h).random=null;
            }
            h=h.next;
        }
        return res;
    }

    Map<Node,Node> map=new HashMap<>();
    //回溯
    public Node copyRandomList2(Node head) {
        if (head == null)  return null;
        if(!map.containsKey(head)){
            map.put(head,new Node(head.val));
            map.get(head).next=copyRandomList2(head.next);
            map.get(head).random=copyRandomList2(head.random);
        }
        return map.get(head);
    }

    //节点拆分，总共遍历三次吧
    public Node copyRandomList(Node head) {
        if (head == null)  return null;
        for (Node temp = head;temp!=null;temp=temp.next.next){
            Node newNode=new Node(temp.val);
            newNode.next=temp.next;
            temp.next=newNode;
        }

        for(Node temp = head;temp!=null;temp=temp.next.next){
            Node newNode=temp.random;
            temp.next.random= newNode==null?null:newNode.next;
        }

        Node newHead=head.next;
        for(Node temp = head;temp!=null;temp=temp.next){
            Node newNode=temp.next;
            temp.next=temp.next.next;
            newNode.next= newNode.next==null?null:newNode.next.next;
        }
        return newHead;
    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}


